This invention relates to digital computers, and more particularly to interleaving of memory systems in digital computers.
Conventionally, "interleaving" is the process of assigning logical addresses to a plurality of memory units making up a memory system such that sequential logical addresses correspond to physical addresses of memory locations in different units. A memory location is the smallest independently accessible portion of the memory system, and can store, e.g., an eight-bit byte of data.
Interleaving is usually expressed in terms of the number of units interleaved together. For example, a system described as having four-way or four-level interleaving (i.e., as having an interleaving factor of four) can be thought of as being divided into four units whose addresses are interleaved together. The four units may be assigned addresses as follows: the locations of the first unit may be assigned addresses 0, 4, 8, 12, etc., the locations of the second unit may be assigned addresses 1, 5, 9, 13, and so forth.
Preferably, each of a plurality of the memory units are accessible independently of the other memory units. Accordingly, for accessing data located at a series of sequential addresses, interleaving permits the memory system to operate in an "overlapping" fashion, i.e., fetching data from different ones of the independently-accessible memory units at approximately the same time. This permits the interleaved memory system to provide the data faster than a non-interleaved memory system.
Generally speaking, the greater the number of level of interleaving, the faster the data can be provided. Thus, four-way interleaving can provide data roughly twice as fast as two-way interleaving. Accordingly, it is generally desirable to maximize the number of levels of memory interleaving.
The time required for data to be supplied from a memory system is generally referred to as "latency". Maximizing the number of levels of memory interleaving can reduce overall latency, i.e., memory access time. Viewed another way, maximizing the number of levels of memory interleaving, or reducing latency, results in increased data throughput in the system.
Moreover, by providing a maximum number of levels of interleaving of independently accessible memory units, memory "conflicts" can be minimized as well. Conflicts arise when the same memory unit is being accessed in separate, overlapping memory operations (e.g., read and/or write operations). Generally, the overlapping operations must be queued, and serviced one at a time by the unit. Accordingly, memory conflicts tend to reduce system throughput. Minimizing memory conflicts avoids this undesirable result.
Heretofore, known interleaving methods have placed significant constraints on the physical structure of the memory units that can be interleaved together, and this, in turn, tends to limit the interleaving factors that can be employed in interleaving memory systems.
To understand the nature of the constraints, consider a known memory system, which includes a number of memory modules of the same or different capacities (i.e., sizes). Each memory module has the same number of independently-accessible banks. Essentially, each memory module includes a data path connected, for example, to the main bus of a computer for communication with, e.g., one or more central processing units.
Such a memory system can be interleaved using a known type of interleaving that employs what we can call "vertical stacking." Vertical stacking may best be understood by considering the following example: a memory system includes a module containing 128 megabytes, and two modules containing 64 megabytes each. The memory system can be configured using vertical stacking, which permits the system to be two-way interleaved.
Specifically, the two 64-megabyte modules can be "stacked vertically" for purposes of addressing, so as to form a structure equal in capacity to the 128-megabyte unit. Then, addresses can be assigned, e.g., with addresses 0, 2, 4, . . . 254 assigned to the 128-megabyte module, addresses 1, 3, . . . 127 assigned to the "bottom" one of the stacked 64-megabyte memories, and addresses 129, 131, . . . 255 assigned to the "top" one of the stacked 64-megabyte modules. In other words, the addresses alternate between the larger module and the smaller modules. This same addressing scheme would be used even if the larger module had two banks of 64 megabytes. Where the larger module does have two banks, the addresses assigned to that larger module may be alternated between the two banks.
Consequently, vertical stacking treats each module as an integral unit for interleaving with other modules of the system, without regard to the existance of independently-accessable banks within the modules.
It would be desirable to interleave the modules of a memory system to a higher level of interleaving than has heretofore been achieved with conventional vertical stacking, thereby reducing latency and conflicts within the system.